package com.cjm.algorithm.backtracking;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Ti51 {
    public static void main(String[] args) {
        Ti51 ti51 = new Ti51();
        List<List<String>> lists = ti51.solveNQueens(5);
        System.err.println("OK");
    }
    public List<List<String>> solveNQueens(int n) {
        String[][] xx = new String[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                xx[i][j] = ".";
            }
        }
        method51(n, 0, xx);
        return res;
    }

    List<List<String>> res = new ArrayList<>();
    private void method51(int n, int row, String[][] chessboard) {
        if (row == n) {
            // 将棋盘加入到结果集中去
            List<String> hel = new ArrayList<>();
            for (int l = 0; l < n; l++) {
                hel.add(String.join("", chessboard[l]));
            }
            res.add(hel);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (valid(row, col, chessboard, n)) {
                chessboard[row][col] = "Q";
                method51(n, row+1, chessboard);
                chessboard[row][col] = ".";
            }
        }
    }

    private boolean valid(int row, int col, String[][] chessboard, int n) {
        // 检测列
        for (int i = 0; i < row; i++) {
            if (chessboard[i][col] != null && chessboard[i][col].equals("Q")) {
                return false;
            }
        }

        // 左下
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (chessboard[i][j] != null && chessboard[i][j].equals("Q")) {
                return false;
            }
        }
        // 右下
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (chessboard[i][j] != null && chessboard[i][j].equals("Q")) {
                return false;
            }
        }
        return true;
    }
}
